package com.lfg.leetcode.leetcode100;


import com.lfg.leetcode.leetcode0.ListNode;

import java.util.HashSet;
import java.util.Set;

public class No142detectCycle {

    public static void main(String[] args) {
        ListNode list = ListNode.deserialize("[-1,-7,7,-4,19,6,-9,-5,-2,-5]");
        int pos = 6;
        ListNode tail = list;
        ListNode node = null;
        while (null != tail.next) {
            pos--;
            if (null == node && pos < 0) {
                node = tail;
            }
            tail = tail.next;
        }
        tail.next = node;
        ListNode ret = detectCycle(list);
        System.out.println(ret.val);
    }

    public static ListNode detectCycle(ListNode head) {
        Set<ListNode> data = new HashSet<>(100);
        while (head != null) {
            if (data.contains(head)) {
                return head;
            }
            data.add(head);
            head = head.next;
        }
        return null;
    }
}
